package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-12
 * Time: 7:46
 */
public class TestDemo {
    // 判断二叉树是不是搜索二叉树

    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    //左树的最大值是否比x大,右树的最小值是否比x小
    //左树要是搜索二叉树
    //右树要是搜索二叉树

    static class Info{
        public boolean isSearch;
        public int maxVal;
        public int minVal;

        public Info(boolean isSearch,int maxVal,int minVal){
            this.isSearch = isSearch;
            this.maxVal = maxVal;
            this.minVal = minVal;
        }
    }

    public static Info process(TreeNode x){
        if(x==null) return null;
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int maxVal = x.val;
        if(leftInfo!=null){
            maxVal = Math.max(maxVal,leftInfo.maxVal);
        }
        if(rightInfo!=null){
            maxVal = Math.max(maxVal,rightInfo.maxVal);
        }
        int minVal = x.val;
        if(leftInfo!=null){
            minVal = Math.min(minVal,leftInfo.minVal);
        }
        if(rightInfo!=null){
            minVal = Math.min(minVal,rightInfo.minVal);
        }
        boolean isSearch = true;
        if(leftInfo!=null&&!leftInfo.isSearch){
            isSearch = false;
        }
        if(rightInfo!=null&&!rightInfo.isSearch){
            isSearch = false;
        }
        if(leftInfo!=null&&x.val<=leftInfo.maxVal){
            isSearch = false;
        }
        if(rightInfo!=null&&x.val>=rightInfo.minVal){
            isSearch = false;
        }

        return new Info(isSearch,maxVal,minVal);
    }


    public static boolean isBinarySearchTree(TreeNode head){
        if(head==null) return false;
        return process(head).isSearch;
    }


    public static void main(String[] args) {


    }

}
